package dfs_bfs.jz38;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/1 21:33
 */
public class Solution1 {

    Set<String> res = new HashSet<>();

    public String[] permutation(String s) {
        dfs(s.toCharArray(), 0);
        String[] ans = new String[res.size()];
        Iterator it = res.iterator();
        int i = 0;
        while (it.hasNext()) {
            ans[i++] = (String) it.next();
        }
        return ans;
    }

    private void dfs(char[] cs, int c) {
        if (c == cs.length) {
            res.add(String.valueOf(cs));
            return;
        }
        for (int i = c; i < cs.length; i++) {
            // 首先交换两个元素之间的位置
            swap(cs, i, c);
            dfs(cs, c + 1);
            swap(cs, i, c);  // 交换回来
        }
    }

    private void swap(char[] cs, int i, int j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
    }
}
